package com.lw.leetcode.other.b;

/**
 * Created with IntelliJ IDEA.
 * other
 * 2311. 小于等于 K 的最长二进制子序列
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/20 14:08
 */
public class LongestSubsequence {


    public static void main(String[] args) {
        LongestSubsequence test = new LongestSubsequence();

        // 5
//        String str = "1001010";
//        int k = 5;

        // 5
        String str = "00101001";
        int k = 1;

        int i = test.longestSubsequence(str, k);
        System.out.println(i);
    }

    public int longestSubsequence(String s, int k) {
        int length = s.length();
        int i = length - 1;
        long v = 0;
        int count = 0;
        for (; i >= 0; i--) {
            long t = s.charAt(i) - '0';
            if (t == 1) {
                v += (t << (length - 1 - i));
            }
            if (v > k) {
                break;
            }
            count++;
        }

        for (; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                count++;
            }
        }
        return count;
    }

}
